843. Перестановки букв

Дана строка, состоящая из m символов. Выведите все перестановки символов заданной строки.

Вход. Одна строка из m (2 ≤ m ≤ 8) символов – букв латинского алфавита и цифр.

Выход. Выведите все перестановки заданной строки в лексикографическом порядке.

Пример входа	Пример выхода
AB	AB BA

РЕШЕНИЕ

комбинаторика - перебор

Анализ алгоритма

В задаче следует сгенерировать все перестановки букв в заданной строке. Это можно сделать, например, при помощи функции next_permutation.

Реализация алгоритма

Читаем входную строку в символьный массив s. Вычисляем ее длину len.

gets(s); len = strlen(s);

Сортируем буквы в возрастающем порядке. В результате сортировки строка s содержит лексикографически наименьшую перестановку.

sort(s, s + len);

Генерируем и выводим все перестановки букв в строке s.

do

{

puts(s);

} while (next_permutation(s, s + len));

Реализация алгоритма – STL

Читаем входную строку.

cin >> s;

Сортируем буквы в возрастающем порядке. В результате сортировки строка s содержит лексикографически наименьшую перестановку.

sort(s.begin(), s.end());

Генерируем и выводим все перестановки букв в строке s.

do

{

cout << s << endl;

} while (next_permutation(s.begin(), s.end()));